#并查集
class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n
        self.cnt = n
        self.groups = {}

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        self.cnt -= 1

    # 记录每个集合的所有关联数据
    def record(self,i):
        group_id = self.find(i)
        if group_id not in self.groups:
            self.groups[group_id] = []
        if i not in self.groups[group_id]:
            self.groups[group_id].append(i)


